Demand for Virtual Machines (VMs) is rising as businesses continue to realize the benefits of virtual computing solutions over obtaining and deploying physical computing resources of their own. These benefits include flexibility in terms of both scalability and cost as businesses can deploy more VMs as computing needs increase and less VMs as computing needs decrease. Furthermore, because businesses are basically “renting” physical resources when they request the VM service provider to deploy a VM, difficulties associated with appropriately scaling and managing physical resources are a burden to the VM service providers—not the businesses. In particular, VM service providers are faced with the difficult task of optimizing physical resource usage levels to mitigate costs associated with idle physical resources while still having adequate physical resources available to service current and future client reservations. Achieving optimal physical resource usage levels requires VM service providers to continually forecast future demand for virtual computing solutions, e.g. to determine how many new data centers and/or computing clusters to deploy. Furthermore, VM service providers must also accept or deny requests to immediately deploy VMs and/or accept reservations for future VMs with imperfect information regarding current physical resource usage levels, e.g. current remaining capacities may be unknown. Denying a request when adequate physical resources are available results in under usage of physical resources whereas accepting a request without adequate physical resources available to service the request may result in failed attempt to deploy the VMs.
It is with respect to these considerations and others that the disclosure made herein is presented.